10003 - Cutting sticks/10003.4.cpp

   1 #include <iostream>
   2 #include <map>
   3 #include <algorithm>
   4 #include <climits>
   5 #include <vector>
   6
   7 using namespace std;
   8
   9 vector<int> p;
  10 int cache[1001][1001];
  11
  12 int f(int i, int j){
  13   if (cache[i][j] != -1){
  14     return cache[i][j];
  15   }
  16   if (j < i) swap(i, j);
  17
  18   for (int k=0; k<p.size()-1; ++k){
  19     if (p[k] <= i && i <= p[k+1] &&
  20         p[k] <= j && j <= p[k+1]){
  21       return cache[i][j] = 0;
  22     }
  23   }
  24
  25   int min = INT_MAX;
  26   for (int k=0; k<p.size(); ++k){
  27     if (i < p[k] && p[k] < j){
  28       int q = j - i + f(i, p[k]) + f(p[k], j);
  29       if (q < min){
  30         min = q;
  31       }
  32     }
  33   }
  34   return   cache[i][j] = min;
  35
  36 }
  37
  38 int main(){
  39   int l;
  40   while (cin >> l && l > 0){
  41     int n;
  42     cin >> n;
  43     p = vector<int>(n+2);
  44     p[0] = 0;
  45     p[n+1] = l;
  46     for (int i=1; i<=n; ++i){
  47       cin >> p[i];
  48     }
  49     for (int i=0;i<=n+1;++i){
  50       for (int j=i;j<=n+1;++j){
  51         cache[p[i]][p[j]]=-1;
  52       }
  53     }
  54     cout << "The minimum cutting is " << f(0, l) << ".\n";
  55   }
  56   return 0;
  57 }